/* WUGraph.java */

package graph;

import java.util.Hashtable;
import list.*;

/**
 * The WUGraph class represents a weighted, undirected graph.  Self-edges are
 * permitted.
 */


public class WUGraph {

	protected DList vertexList;
	protected Hashtable<Object, DListNode> vertexHash;
	protected Hashtable<VertexPair, DListNode> edgeHash;
	protected int edgeCount;

	/**
	 * WUGraph() constructs a graph having no vertices or edges.
	 *
	 * Running time:  O(1).
	 */
	public WUGraph() {
		vertexList = new DList();
		vertexHash = new Hashtable<Object, DListNode>();
		edgeHash = new Hashtable<VertexPair, DListNode>();
		edgeCount =0;
	}


	/**
	 * vertexCount() returns the number of vertices in the graph.
	 *
	 * Running time:  O(1).
	 */
	public int vertexCount() {
		return vertexList.length();
	}

	/**
	 * edgeCount() returns the number of edges in the graph.
	 *
	 * Running time:  O(1).
	 */
	public int edgeCount() {
		return edgeCount;
	}

	/**
	 * getVertices() returns an array containing all the objects that serve
	 * as vertices of the graph.  The array's length is exactly equal to the
	 * number of vertices.  If the graph has no vertices, the array has length
	 * zero.
	 *
	 * (NOTE:  Do not return any internal data structure you use to represent
	 * vertices!  Return only the same objects that were provided by the
	 * calling application in calls to addVertex().)
	 *
	 * Running time:  O(|V|).
	 */
	public Object[] getVertices() {
		Object[] result = new Object[vertexCount()];
		DListNode temp = vertexList.front();

		for (int i = 0; i < vertexCount(); i++) {
			result[i] = ((Vertex) (temp.item())).vertex();
			temp = vertexList.next(temp);			
		}

		return result;
	}

	/**
	 * addVertex() adds a vertex (with no incident edges) to the graph.  The
	 * vertex's "name" is the object provided as the parameter "vertex".
	 * If this object is already a vertex of the graph, the graph is unchanged.
	 *
	 * Running time:  O(1).
	 */
	public void addVertex(Object vertex){
		if (isVertex(vertex)) {		// vertex is already in "this"
			return;
		} else {
			vertexList.insertBack(new Vertex(vertex));
			vertexHash.put(vertex, vertexList.back());
		}
	}


	/**
	 * removeVertex() removes a vertex from the graph.  All edges incident on the
	 * deleted vertex are removed as well.  If the parameter "vertex" does not
	 * represent a vertex of the graph, the graph is unchanged.
	 *
	 * Running time:  O(d), where d is the degree of "vertex".
	 */
	public void removeVertex(Object vertex) {
		if (isVertex(vertex) ) {
			DList edgeList = edgeList(vertex);
			DListNode currentEdgeNode = edgeList.front();
			VertexPair edge;
			Object otherVertex;

			while (currentEdgeNode != null) {

				edge = ((Edge)currentEdgeNode.item() ).edge();
				otherVertex = edge.otherVertex(vertex);
				removeEdge(vertex, otherVertex);

				currentEdgeNode = edgeList.front();
			}

			DListNode vertexNode = (DListNode) vertexHash.get(vertex);
			vertexHash.remove(vertex);
			vertexList.remove(vertexNode);
		}
	}

	/**
	 * isVertex() returns true if the parameter "vertex" represents a vertex of
	 * the graph.
	 *
	 * Running time:  O(1).
	 */
	public boolean isVertex(Object vertex) {
		return vertexHash.containsKey(vertex);
	}

	/**
	 * degree() returns the degree of a vertex.  Self-edges add only one to the
	 * degree of a vertex.  If the parameter "vertex" doesn't represent a vertex
	 * of the graph, zero is returned.
	 *
	 * Running time:  O(1).
	 */
	public int degree(Object vertex) {
		if ( isVertex(vertex) ) {
			return edgeList(vertex).length();
		} else {
			return 0;
		}
	}

	/**
	 * getNeighbors() returns a new Neighbors object referencing two arrays.  The
	 * Neighbors.neighborList array contains each object that is connected to the
	 * input object by an edge.  The Neighbors.weightList array contains the
	 * weights of the corresponding edges.  The length of both arrays is equal to
	 * the number of edges incident on the input vertex.  If the vertex has
	 * degree zero, or if the parameter "vertex" does not represent a vertex of
	 * the graph, null is returned (instead of a Neighbors object).
	 *
	 * The returned Neighbors object, and the two arrays, are both newly created.
	 * No previously existing Neighbors object or array is changed.
	 *
	 * (NOTE:  In the neighborList array, do not return any internal data
	 * structure you use to represent vertices!  Return only the same objects
	 * that were provided by the calling application in calls to addVertex().)
	 *
	 * Running time:  O(d), where d is the degree of "vertex".
	 */
	public Neighbors getNeighbors(Object vertex) {
		if (isVertex(vertex) && degree(vertex) > 0) {

			Neighbors result = new Neighbors();
			result.weightList = new int[degree(vertex)];
			result.neighborList = new Object[degree(vertex)];

			DList edgeList = edgeList(vertex);
			DListNode edgeNode = edgeList.front();
			Edge edge;

			for (int i = 0; i < degree(vertex); i++) {
				edge = (Edge) edgeNode.item();

				result.weightList[i] = edge.weight();
				result.neighborList[i] = edge.edge().otherVertex(vertex);

				edgeNode = edgeList.next(edgeNode);
			}

			return result;

		} else {
			return null;
		}
	}

	/**
	 * addEdge() adds an edge (u, v) to the graph.  If either of the parameters
	 * u and v does not represent a vertex of the graph, the graph is unchanged.
	 * The edge is assigned a weight of "weight".  If the edge is already
	 * contained in the graph, the weight is updated to reflect the new value.
	 * Self-edges (where u == v) are allowed.
	 *
	 * Running time:  O(1).
	 */
	public void addEdge(Object u, Object v, int weight) {
		DListNode uEdgeListNode;
		DListNode vEdgeListNode;
		DList uEdgeList;
		DList vEdgeList;
		Edge uEdge;
		Edge vEdge;
		VertexPair edge;

		if (isEdge(u, v)) {
			removeEdge(u, v);
		}

		if (isVertex(v) && isVertex(v) ) {
			edge = new VertexPair(u, v);

			uEdge = new Edge(null, edge, weight);
			vEdge = new Edge(null, edge, weight);

			uEdgeList = edgeList(u);
			vEdgeList = edgeList(v);

			if (uEdgeList == vEdgeList) {
				uEdgeList.insertFront(uEdge);
				uEdgeListNode = (uEdgeList.front());

			} else {

				uEdgeList.insertFront(uEdge);
				vEdgeList.insertFront(vEdge);

				uEdgeListNode = (uEdgeList.front());
				vEdgeListNode = (vEdgeList.front());		

				( (Edge)(uEdgeListNode.item()) ).setPartner(vEdgeListNode);
				( (Edge)(vEdgeListNode.item()) ).setPartner(uEdgeListNode);
			}

			edgeHash.put(edge, uEdgeListNode);
			edgeCount++;
		}

	}

	/**
	 * removeEdge() removes an edge (u, v) from the graph.  If either of the
	 * parameters u and v does not represent a vertex of the graph, the graph
	 * is unchanged.  If (u, v) is not an edge of the graph, the graph is
	 * unchanged.
	 *
	 * Running time:  O(1).
	 */
	public void removeEdge(Object u, Object v) {
		if (isVertex(u) && isVertex(v) && isEdge(u, v)) {

			VertexPair edge = new VertexPair(u,v);

			DListNode edgeNode = (DListNode) edgeHash.get(edge);
			DListNode partnerEdgeNode = ( (Edge) edgeNode.item() ).partner();

			edgeHash.remove(edge);		// remove edge from hashtable

			DList uEdgeList = edgeList(u);
			DList vEdgeList = edgeList(v);

			if (partnerEdgeNode == null) {		//(u==v) and edge is a self edge
				uEdgeList.remove(edgeNode);
			} else {

				if (uEdgeList.validNode(edgeNode)) {		// remove edge from DList
					uEdgeList.remove(edgeNode);
					vEdgeList.remove(partnerEdgeNode);
				} else {
					vEdgeList.remove(edgeNode);
					uEdgeList.remove(partnerEdgeNode);
				}
			}
			edgeCount--;
		}

	}

	/**
	 * isEdge() returns true if (u, v) is an edge of the graph.  Returns false
	 * if (u, v) is not an edge (including the case where either of the
	 * parameters u and v does not represent a vertex of the graph).
	 *
	 * Running time:  O(1).
	 */
	public boolean isEdge(Object u, Object v) {
		VertexPair edge = new VertexPair(u, v);
		return edgeHash.containsKey(edge);
	}

	/**
	 * weight() returns the weight of (u, v).  Returns zero if (u, v) is not
	 * an edge (including the case where either of the parameters u and v does
	 * not represent a vertex of the graph).
	 *
	 * (NOTE:  A well-behaved application should try to avoid calling this
	 * method for an edge that is not in the graph, and should certainly not
	 * treat the result as if it actually represents an edge with weight zero.
	 * However, some sort of default response is necessary for missing edges,
	 * so we return zero.  An exception would be more appropriate, but
	 * also more annoying.)
	 *
	 * Running time:  O(1).
	 */
	public int weight(Object u, Object v) {
		if (isEdge(u, v)) {
			VertexPair edge = new VertexPair(u,v);
			DListNode edgeNode = (DListNode) edgeHash.get(edge);
			Edge edge1 = (Edge) edgeNode.item();
			return edge1.weight();
		} else {
			return 0;
		}
	}

	/**
	 * edgeList returns the DList representing the List of edges from "vertex".
	 * If vertex is not in WUGraph return null.
	 * HelperMethod.
	 * 
	 * Running time:  O(1).
	 * 
	 * @return DList corresponding to the edges of vertex
	 */
	protected DList edgeList(Object vertex) {
		if ( isVertex(vertex) ) {
			DListNode vertexNode = (DListNode) vertexHash.get(vertex);
			return ((Vertex)vertexNode.item()).edges();
		} else {
			return null;
		}
	}

	/**
	 * toString() returns the String representation of "this" graph.
	 * 
	 * @return the String representation of "this" graph.
	 */
	public String toString() {
		String result = new String("");
		DListNode vertexNode = vertexList.front();
		Vertex vertex;
		while (vertexNode != null) {
			vertex = (Vertex) vertexNode.item();
			result = result + "\n" + vertex.vertex + "    " + vertex.edges;
			vertexNode = vertexList.next(vertexNode);
		}
		return result;
	}

}
